package com.arithmetic.basics;


import com.util.ListNode;

/**
 * 合并两个有序链表
 * 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
 * 输入：l1 = [1,2,4], l2 = [1,3,4]
 * 输出：[1,1,2,3,4,4]
 */
public class Day8 {
    public static void main(String[] args) {
    }

    /**
     * 文字题解
     * 方法一：递归：在定义一个过程或函数时直接或间接调用自己的成分，称之为递归。递归常被用来描述以自相似方法重复事物的过程-将一个大问题分解为若干个相似小问题解决
     * 思路
     * 我们可以如下递归地定义两个链表里的 merge 操作（忽略边界情况，比如空链表等）：
     * {list1[0]+merge(list1[1:],list2)list1[0]<list2[0]list2[0]+merge(list1,list2[1:])otherwise\left\{ \begin{array}{ll} list1[0] + merge(list1[1:], list2) & list1[0] < list2[0] \\ list2[0] + merge(list1, list2[1:]) & otherwise \end{array} \right.
     * {
     * list1[0]+merge(list1[1:],list2)
     * list2[0]+merge(list1,list2[1:])
     * list1[0]<list2[0]
     * otherwise
     * 也就是说，两个链表头部值较小的一个节点与剩下元素的 merge 操作结果合并。
     * 算法
     * 我们直接将以上递归过程建模，同时需要考虑边界情况。
     * 如果 l1 或者 l2 一开始就是空链表，那么没有任何操作需要合并，所以我们只需要返回非空链表。
     * 否则，我们要判断 l1 和 l2 哪一个链表的头节点的值更小，然后递归地决定下一个添加到结果里的节点。如果两个链表有一个为空，递归结束。
     */

    public ListNode solution(ListNode l1, ListNode l2) {
        // 链表进行判断：如果两个链表有一个为空，递归结束。
        if (l1 == null) {
            return l2;
        } else if (l2 == null) {
            return l1;
        } else if (l1.val < l2.val) {
            l1.next = solution(l1.next, l2);
            return l1;
        } else {
            l2.next = solution(l1, l2.next);
            return l2;
        }
    }
    /**
     * 方法二：迭代：迭代是重复反馈过程的活动，其目的通常是为了逼近所需目标或结果。每一次对过程的重复称为一次"迭代"，而每一次迭代得到的结果会作为下一次迭代的初始值。
     * 解释：为了达到某个目标，不断重复某一件事。
     * 递归中有迭代，但是迭代中不一定含有递归
     * 而迭代，是通过无数次，不断的，重复的，接近一个目标，折返接近，再折返再接近，最终达到目标。
     * 它不是一次性完成的，是通过不断重复的，但每次重复又比之前更好一点，这样一种非线性的进程。
     * 思路
     * 我们可以用迭代的方法来实现上述算法。当 l1 和 l2 都不是空链表时，判断 l1 和 l2 哪一个链表的头节点的值更小，将较小值的节点添加到结果里，当一个节点被添加到结果里之后，将对应链表中的节点向后移一位。
     * 算法
     * 首先，我们设定一个哨兵节点 prehead ，这可以在最后让我们比较容易地返回合并后的链表。我们维护一个 prev 指针，我们需要做的是调整它的 next 指针。然后，我们重复以下过程，直到 l1 或者 l2 指向了 null ：如果 l1 当前节点的值小于等于 l2 ，我们就把 l1 当前的节点接在 prev 节点的后面同时将 l1 指针往后移一位。否则，我们对 l2 做同样的操作。不管我们将哪一个元素接在了后面，我们都需要把 prev 向后移一位。
     * 在循环终止的时候， l1 和 l2 至多有一个是非空的。由于输入的两个链表都是有序的，所以不管哪个链表是非空的，它包含的所有元素都比前面已经合并链表中的所有元素都要大。这意味着我们只需要简单地将非空链表接在合并链表的后面，并返回合并链表即可。
     */
    public ListNode  solution2(ListNode l1,ListNode l2){ // 目标时合并2个链表
        ListNode prehead = new ListNode(1);
        // 装链表的容器
        ListNode prev = prehead;
        while (l1 != null && l2 != null){
            if (l1.val <= l2.val){
                prev.next = l1;
                l1 = l1.next;
            } else {
                prev.next = l2;
                l2 = l2.next;
            }
//            链表合并
            prev = prev.next;
        }
        // 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
        prev.next = l1 == null ? l2 : l1;
        return prehead.next;
    }
}
